import java.util.HashMap;
import java.util.PriorityQueue;

/**
 * 给定一个字符串 s ，根据字符出现的 频率 对其进行 降序排序 。一个字符出现的 频率 是它出现在字符串中的次数。
 * 返回 已排序的字符串。如果有多个答案，返回其中任何一个。
 * */
public class LeetCode451 {
    public String frequencySort(String s) {
        HashMap<Character, Integer> count = new HashMap<>();
        for (char c: s.toCharArray()) {
            count.put(c, count.getOrDefault(c, 0) + 1);
        }
        PriorityQueue<Character> heap = new PriorityQueue<>((char1, char2) -> {
            return -count.get(char1) + count.get(char2);
        });
        StringBuilder res = new StringBuilder();
        count.keySet().forEach(key->{
            heap.add(key);
        });
        while (!heap.isEmpty()) {
            char c = heap.poll();
            for (int i = 0; i < count.get(c); i++) {
                res.append(c);
            }
        }
        return res.toString();
    }
}
